#include <iostream>
using namespace std;
const int N = 1e6 + 10;
long long arr[N];
int main()
{
    arr[1] = 1;
    arr[2] = 2;
    // 直接在中间部分取模即可
    // 不影响结果，这是由于取模的性质决定的
    for (int i = 3; i < N; ++i)
        arr[i] = (arr[i - 2] + arr[i - 1] * 2) % 32767;
    int num = 0, k;
    cin >> num;
    while (num--)
    {
        cin >> k;
        cout << arr[k] << endl;
    }
    return 0;
}